import Queue
import math

class bst:

    class Node:
        value, left, right = None, None, None

    root = None
    def add(self, value):
        this = self
        def ad(node,value):
            if node is None:
                node = this.Node()
                node.left = None
                node.right = None
                node.value = value
            elif value < node.value:
                node.left = ad(node.left,value)
            else:
                node.right = ad(node.right,value)
            return node

        self.root = ad(self.root, value)

    # Different type orders ( in order , pre order , post order , level order and reverse level order)
    def inorder(self):
        def ino(node):
            if node is None:
                return
            ino(node.left)
            print node.value
            ino(node.right)

        ino(self.root)

    def preorder(self):
        def pre(node):
            if node is None:
                return
            pre(node.left)
            pre(node.right)
            print node.value

        pre(self.root)


    def postorder(self):
        def post(node):
            if node is None:
                return
            print node.value
            post(node.left)
            post(node.right)

        post(self.root)


    # TODO : reverse level order


    # spiral level order or zig zag 
    # can be solved with two stacks
    def spiral_level_order(self):
        stack_one = []
        stack_two = []
        stack_one.append(self.root)
        
        while stack_one or stack_two:

            while stack_one:
                pop = stack_one.pop()
                print pop.value
                if pop.left is not None:
                    stack_two.append(pop.left)
                if pop.right is not None:
                    stack_two.append(pop.right)

            while stack_two:
                pop = stack_two.pop()
                print pop.value
                if pop.left is not None:
                    stack_one.append(pop.left)
                if pop.right is not None:
                    stack_one.append(pop.right)



    # print out level wise using queue
    def levelOrder(self):
        q = Queue.Queue()
        q.put(self.root)
        while q:
            try:
                temp = q.get_nowait()
                print temp.value
            except Exception as e:
                break
            if temp.left is not None:
                q.put(temp.left)

            if temp.right is not None:
                q.put(temp.right)

    # left view of the tree returns elements that can be see from the left side the tree
    # left view elements can be present on the right side as well
    # do level order traversal and print the first element of the each level
    # use a flag to notify if the level has reached
    def leftView(self):
        q = Queue.Queue()
        leftValues = []
        q.put(self.root)
        q.put("null")
        print self.root.value

        while q:
            try:
                temp = q.get_nowait()
                if temp == "null":
                    q.put("null")
                    temp = q.get_nowait()
                    # print the first element of the level
                    print temp.value
            except Exception as e:
                break

            if temp.left is not None:
                q.put(temp.left)

            if temp.right is not None:
                q.put(temp.right)


    # find the height of the tree
    def height(self):
        def hei(node):
            if node is None:
                return 0
            return 1+max(hei(node.left), hei(node.right))

        return hei(self.root)

    # find the height from give node

    def heightFromNode(self,node):
        def hei(node):
            if node is None:
                return 0
            return 1+max(hei(node.left), hei(node.right))

        return hei(node)

    # check if the tree is balanced or not
    # the difference of left and right sub trees should be less than or equal to 1
    def isBalanced(self):
        left = self.heightFromNode(self.root.left)
        right = self.heightFromNode(self.root.right)

        diff = math.fabs(left-right)

        if diff > 1:
            return False

        return True

    # find the minimum value in the bst
    def min(self):
        temp = self.root
        while temp.left is not None:
            temp = temp.left

        return temp.value

    # find the maximum value in the bst
    def max(self):
        temp = self.root
        while temp.right is not None:
            temp = temp.right

        return temp.value

    # find paths from root node to all the leafs
    def pathFromRoot(self):
        def paths(node,path=""):
            if node is None:
                return
            path += " "+str(node.value)
            if node.left is not None:
                paths(node.left, path)
            if node.right is not None:
                paths(node.right, path)
            if node.left is None and node.right is None:
                print path

        paths(self.root, "")

    # find out total number of nodes present in binary search tree
    # both left sub tree and right sub tree
    def total_no_nodes(self):
        count = 0
        def total(node, count=0):
            if node is None:
                return count
            count += 1
            count = total(node.left,count)
            count = total(node.right,count)
            return count

        print total(self.root)

    # find total number of leaf nodes present in the binary search tree
    def total_leaf_nodes(self):
        def leaf_nodes(node,count):
            if node is None:
                return count

            if node.left is None and node.right is None:
                count += 1

            count = leaf_nodes(node.left,count)
            count = leaf_nodes(node.right,count)
            return count

        return leaf_nodes(self.root,0)

    def node_value_to_sum_of_children(self):
        pass

''' 
        50 
    25      75
12      60      100
            80
'''

b = bst()
b.add(50)
b.add(25)
b.add(12)
b.add(75)
b.add(60)
b.add(100)
b.add(80)

b.spiral_level_order()
